/*
 * @ Created with Clion
 * @ Author Morbid
 * @ Date 2022/06/12
 * @ Time 11:22
 */

/*!
 * 定义单链表
 * 实现单链表基本操作
 */
typedef int ElemType;
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

/*!
 * 初始化为不带头的单链表
 * @param L 不带头单链表
 */
void InitList_NoneHead(LinkList &L) {
    L = nullptr;
}

/*!
 * 初始化为带头的单链表
 * @param L 带头单链表
 */
void InitList_HaveHead(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode));
    L->data = 0;
    L->next = nullptr;
}

/*!
 * 判断不带头单链表是否为空
 * @param L 不带头单链表
 * @return 如果空返回true，否则返回false
 */
bool Empty_NoneHead(LinkList L) {
    return L == nullptr;
}

/*!
 * 判断带头单链表是否为空
 * @param L 带头单链表
 * @return 如果空返回true，否则返回false
 */
bool Empty_HaveHead(LinkList L) {
    return L->next == nullptr;
}

/*!
 * 在不带头单链表指定位置插入元素
 * @param L 不带头单链表
 * @param i 要插入的位置
 * @param e 要插入的元素
 * @return  插入成功返回true，否则返回false
 */
bool ListInsert_NoneHead(LinkList &L, int i, ElemType e) {
    if (i < 1)
        return false;
    if (i == 1) {
        auto *q = (LNode *) malloc(sizeof(LNode));
        if (q == nullptr)
            return false;
        q->data = e;
        q->next = L;
        L = q;
        return true;
    }
    LNode *p = L;
    for (int j = 1; p != nullptr; j++) {
        if (j == i - 1) {
            auto *q = (LNode *) malloc(sizeof(LNode));
            if (q == nullptr)
                return false;
            q->data = e;
            q->next = p->next;
            p->next = q;
            return true;
        }
        p = p->next;
    }
    return false;
}

/*!
 * 在带头单链表指定位置插入元素
 * @param L 带头单链表
 * @param i 要插入的位置
 * @param e 要插入的元素
 * @return  插入成功返回true，否则返回false
 */
bool ListInsert_HaveHead(LinkList &L, int i, ElemType e) {
    if (i < 1)
        return false;
    LNode *p = L;
    for (int j = 0; p != nullptr; j++) {
        if (j == i - 1) {
            auto *q = (LNode *) malloc(sizeof(LNode));
            if (q == nullptr)
                return false;
            q->data = e;
            q->next = p->next;
            p->next = q;
            return true;
        }
        p = p->next;
    }
    return false;
}

/*!
 * 在指定节点的后面添加元素
 * @param p 指定节点
 * @param e 要添加的元素
 * @return  添加成功返回true,否则返回false
 */
bool InsertNextNode(LNode *p, ElemType e) {
    if (p == nullptr)
        return false;
    auto *q = (LNode *) malloc(sizeof(LNode));
    if (q == nullptr)
        return false;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
}

/*!
 * 在指定节点的前面面添加元素
 * @param p 指定节点
 * @param e 要添加的元素
 * @return  添加成功返回true,否则返回false
 */
bool InsertPriorNode(LNode *p, ElemType e) {
    if (p == nullptr)
        return false;
    auto *q = (LNode *) malloc(sizeof(LNode));
    if (q == nullptr)
        return false;
    q->next = p->next;
    p->next = q;
    q->data = p->data;
    p->data = e;
    return true;
}

/*!
 * 按位置删除不带头单链表节点
 * @param L 不带头单链表
 * @param i 节点位置
 * @param e 删除节点的数据
 * @return
 */
bool ListDelete_NoneHead(LinkList &L, int i, ElemType &e) {
    if (i < 1 || Empty_NoneHead(L))
        return false;
    if (i == 1) {
        LNode *q = L;
        L = q->next;
        free(q);
        return true;
    }
    LNode *p = L;
    for (int j = 1; p->next != nullptr; j++) {
        if (j == i - 1) {
            LNode *q = p->next;
            e = q->data;
            p->next = q->next;
            free(q);
            return true;
        }
        p = p->next;
    }
    return false;
}


/*!
 * 按位置删除带头单链表节点
 * @param L 带头单链表
 * @param i 节点位置
 * @param e 删除节点的数据
 * @return 删除成功返回true,否则返回false
 */
bool ListDelete_HaveHead(LinkList &L, int i, ElemType &e) {
    if (i < 1 || Empty_HaveHead(L))
        return false;
    LNode *p = L;
    for (int j = 0; p->next != nullptr; j++) {
        if (j == i - 1) {
            LNode *q = p->next;
            e = q->data;
            p->next = q->next;
            free(q);
            return true;
        }
        p = p->next;
    }
    return false;
}

/*!
 * 删除指定节点(不能删除最后一个节点)
 * @param p 要删除的节点
 * @return 删除成功返回true,否则返回false
 */
bool DeleteNode(LNode *p) {
    if (p == nullptr || p->next == nullptr)
        return false;
    LNode *q = p->next;
    p->data = q->data;
    free(q);
    return true;
}

/*!
 * 按位置查找不带头单链表节点
 * @param L 不带头单链表
 * @param i 节点位置
 * @return 查找到的节点
 */
LNode *GetElem_NoneHead(LinkList L, int i) {
    if (i < 1)
        return nullptr;
    LNode *p = L;
    for (int j = 0; p != nullptr && j < i - 1; j++)
        p = p->next;
    return p;
}

/*!
 * 按位置查找带头单链表节点
 * @param L 带头单链表
 * @param i 节点位置
 * @return 查找到的节点，查找失败返回空指针
 */
LNode *GetElem_HaveHead(LinkList L, int i) {
    if (i < 0)
        return nullptr;
    LNode *p = L;
    for (int j = 0; p != nullptr && j < i; j++)
        p = p->next;
    return p;
}

/*!
 * 按值查找不带头单链表节点
 * @param L 不带头单链表
 * @param e 要查找的值
 * @return 查找到的节点，查找失败返回空指针
 */
LNode *LocateElem_NoneHead(LinkList L, ElemType e) {
    LNode *p = L;
    while (p != nullptr && p->data != e)
        p = p->next;
    return p;
}

/*!
 * 按值查找带头单链表节点
 * @param L 带头单链表
 * @param e 要查找的值
 * @return 查找到的节点，查找失败返回空指针
 */
LNode *LocateElem_HaveHead(LinkList L, ElemType e) {
    LNode *p = L->next;
    while (p != nullptr && p->data != e)
        p = p->next;
    return p;
}

/*!
 * 获取不带头单链表长度
 * @param L 不带头单链表
 * @return 该链表长度
 */
int Length_NoneHead(LinkList L) {
    int len = 0;
    LNode *p = L;
    while (p != nullptr) {
        p = p->next;
        len++;
    }
    return len;
}

/*!
 * 获取带头单链表长度
 * @param L 带头单链表
 * @return 该链表长度
 */
int Length_HaveHead(LinkList L) {
    int len = 0;
    LNode *p = L;
    while (p->next != nullptr) {
        p = p->next;
        len++;
    }
    return len;
}